package top.truism.leetcode;

import java.util.Arrays;

/**
 * 在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。
 * Rick 有n个空的篮子，第i个篮子的位置在position[i]，Morty想把m个球放到这些篮子里，
 * 使得任意两球间最小磁力最大。
 *
 * 已知两个球如果分别位于x和y，那么它们之间的磁力为|x - y|。
 *
 * 给你一个整数数组position和一个整数m，请你返回最大化的最小磁力。
 *
 */
public class LeetCode1552 {

    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1, right = position[position.length-1] - position[0], ans = -1;
        while (left <= right) {
            int mid = (left + right)/2;
            if(check(mid, position, m)) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }

    /**
     * 判断以当前最小距离x，在position数组中是否可以放m个球
     *
     * @param x
     * @param position
     * @param m
     * @return
     */
    private boolean check(int x, int[] position, int m) {
        // pre 代表第一个球的位置, cnt代表当前存放的球的数量
        int pre = position[0], cnt = 1;
        for (int i = 1; i < position.length; i++) {
            // 如果当前位置与前一个位置大于等于x，则可以放球, cnt++
            if(position[i] - pre >= x) {
                pre = position[i];
                cnt += 1;
            }
        }
        return cnt >= m;
    }

}
